//
// Created by Semir on 2020/5/15.
//

#include <iostream>
#include <deque>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void ConnectTreeNode(TreeNode* pRoot, TreeNode* pLeft, TreeNode* pRight) {
    if (pRoot == nullptr) {
        return;
    }
    pRoot->left = pLeft;
    pRoot->right = pRight;
}

TreeNode* BuildTree1() {
    auto* node1 = new TreeNode(8);
    auto* node2 = new TreeNode(6);
    auto* node3 = new TreeNode(6);
    auto* node4 = new TreeNode(5);
    auto* node5 = new TreeNode(7);
    auto* node6 = new TreeNode(7);
    auto* node7 = new TreeNode(5);
    ConnectTreeNode(node1, node2, node3);
    ConnectTreeNode(node2, node4, node5);
    ConnectTreeNode(node3, node6, node7);
    return node1;
}

bool check(deque<TreeNode*> Q) {
    if (Q.size() < 2) {
        return true;
    }
    while (!Q.empty()) {
        TreeNode* pLeft = Q.front();
        TreeNode* pRight = Q.back();
        Q.pop_front();
        Q.pop_back();
        if (pLeft == nullptr && pRight == nullptr) {
            continue;
        }
        if (pLeft == nullptr || pRight == nullptr) {
            return false;
        }
        if (pLeft->val != pRight->val) {
            return false;
        }
    }
    return true;
}

bool isSymmetrical(TreeNode* pRoot) {
    if (pRoot == nullptr) {
        return true;
    }
    deque<TreeNode*> Q;
    TreeNode* pNode = pRoot;
    auto* mkNode = new TreeNode(0);
    Q.push_back(pNode);
    Q.push_back(mkNode);
    while (!Q.empty()) {
        pNode = Q.front();
        if (pNode != mkNode) {
            Q.pop_front();
            if (pNode) {
                Q.push_back(pNode->left);
                Q.push_back(pNode->right);
            }
        } else {
            if (Q.size() == 1) {
                break;
            }
            Q.pop_front();
            if (!check(Q)) {
                return false;
            }
            Q.push_back(mkNode);
        }
    }
    return true;
}

int main() {
    TreeNode* pRoot = BuildTree1();
    bool res = isSymmetrical(pRoot);
    cout << res << endl;
    return 0;
}